/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  //计算数组和
  let sum = nums.reduce((acc, num) => acc + num, 0)

  //数组长度
  let n = nums.length
  //数组和为奇数，返回false
  if (sum % 2 === 1) return false

  //目标值
  let target = sum / 2
  //dp[i][j]表示处理完前i个元素后是否能构成j
  let dp = Array.from({ length: n + 1 }, () => new Array(target + 1).fill(false))
  //初始化
  for (let i = 0; i <= n; i++) {
    dp[i][0] = true
  }
  //状态转移方程：从第一行处理到第n行，对应的数组元素的索引是0~n-1
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= target; j++) {
      if (nums[i - 1] > j) {//当前元素大于目标值，不能选当前元素
        dp[i][j] = dp[i - 1][j]
      } else {//反之，当前元素可选可不选
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]]
      }
    }
  }

  //返回结果
  return dp[n][target]
};

console.log(canPartition([1, 5, 5, 11]))
